package org.regotto.basics.monotonous;

/**
 * 单调栈, 使用栈结构存储数据, 且栈内数据总是保持单调的
 * 求每个数左边第一个比它小的数
 * 1 4 3 5
 * 5 左边第一个比它小的是是 3
 * 3 左边第一个比它小的是 1
 */
public class MonotonousStack {

    public static void main(String[] args) {
        int[] q = {1, 4, 3, 5};
        first(q, q.length);

    }

    /**
     * 求每个数左边第一个比它小的数
     * 1 4 3 5
     * 5 左边第一个比它小的是是 3
     * 3 左边第一个比它小的是 1
     * @param q 传入的数组
     * @param n 数组长度
     */
    public static void first(int[] q, int n) {
        int t = 0;
        int[] s = new int[100];
        for (int i = 0; i < n; i++) {
            while (t != 0 && s[t] >= q[i]) t--;
            if (t != 0) System.out.println(s[t]);
            s[++t] = q[i];
        }
    }

}
